class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k)
    {
        int m = 0, n = nums.size();
        int Min = INT_MAX;
        for (auto e : nums)
        {
            if (e < 0) m++;
            Min = min(Min, abs(e));
        }
        int sum = 0;

        if (m > k)
        {
            sort(nums.begin(), nums.end());
            for (int i = 0; i < k; i++)
            {
                sum += -nums[i];
            }
            for (int i = k; i < n; i++)
            {
                sum += nums[i];
            }
        }
        else
        {
            for (auto e : nums) sum += abs(e);
            if ((k - m) % 2)
                sum -= 2 * Min;
        }
        return sum;

    }
};